﻿// DataStructure.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <stdio.h>
#include <stdlib.h>

namespace Y190606_BS {
int main();

#define MAXSIZE 10
#define NotFound 0
typedef int ElementType;

typedef int Position;
typedef struct LNode* List;
struct LNode {
	ElementType Data[MAXSIZE];
	Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标1开始存储 */
Position BinarySearch(List L, ElementType X);

int main()
{
	LNode a;
	a.Last = 5;
	a.Data[1] = 12;
	a.Data[2] = 31;
	a.Data[3] = 55;
	a.Data[4] = 89;
	a.Data[5] = 101;
	/*
	a.Last = 3;
	a.Data[1] = 26;
	a.Data[2] = 78;
	a.Data[3] = 233;
	//*/
	List L;
	ElementType X;
	Position P;

	//L = ReadInput();
	L = &a;
	scanf("%d", &X);
	P = BinarySearch(L, X);
	printf("%d\n", P);

	return 0;
}

Position BinarySearch(List L, ElementType X)
{
	int high = L->Last;
	int low = 1;
	int pos = 0;
	while (high - low > 1) {
		pos = (high + low) / 2;
		if (L->Data[pos] == X)
			return pos;
		else if (L->Data[pos] > X) {
			high = pos;
		}
		else {
			low = pos;
		}
	}
	if (L->Data[low] == X)
		return low;
	if (L->Data[high] == X)
		return high;
	return NotFound;
}

}

int main_190606_BS()
{
	Y190606_BS::main();
	return 0;
}

